package recursion

import "strconv"

func longestPalindrome(s string) string {
	ansS := 0
	ansE := 0
	resMap := map[string]bool{}
	var fn = func(i, j int) {
		if j-i > ansE - ansS {
			ansS, ansE = i, j
		}
	}
	PalindromeProcess(s, fn, resMap)
	return 	s[ansS:ansE+1]
}

func PalindromeProcess(s string, fn func(int, int), resMap map[string]bool) {
	for i:=0; i<len(s); i++ {
		for j:=i; j<len(s); j++ {
			IsPalindromeProcess(s, i, j, fn, resMap)
		}
	}
}

func IsPalindromeProcess(s string, L, R int, fn func(int, int),  resMap map[string]bool) bool {
	key := strconv.Itoa(L) + "_" + strconv.Itoa(R)
	if v, ok := resMap[key]; ok {
		return v
	}
	if L == R {
		resMap[key] = true
		return resMap[key]
	}
	if s[L] == s[R] && R-L == 1 {
		fn(L, R)
		resMap[key] = true
		return resMap[key]
	} else if s[L] == s[R]  && IsPalindromeProcess(s, L+1, R-1, fn, resMap) {
		fn(L, R)
		resMap[key] = true
		return resMap[key]
	}
	resMap[key] = false
	return resMap[key]
}
